#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k)
    {
        struct point
        {
            int _val, _x, _y;

            point(int val, int x, int y)
                : _val(val), _x(x), _y(y)
            { }

            bool operator>(const point& p) const
            {
                return this->_val > p._val;
            }
        };

        std::priority_queue<point, std::vector<point>, std::greater<point>> heap;

        int n = matrix.size();
        for (int i = 0; i < n; ++i)
        {
            heap.emplace(matrix[i][0], i, 0);
        }

        for (int i = 0; i < k - 1; ++i)
        {
            point cur = heap.top();
            heap.pop();

            if (cur._y < n - 1)
            {
                heap.emplace(matrix[cur._x][cur._y + 1], cur._x, cur._y + 1);
            }
        }

        return heap.top()._val;
    }
};